package algorithm;

/**
 * 判断链表回文， 1->2->3->3->2->1->null
 * 方法1：利用栈实现方式， 空间复杂度为O(n) 时间复杂度O(n)
 * 方法2: 利用快慢指针，  降低空间复杂度为O(n/2)
 * 方法3：利用快慢指针，不借助栈，快指针指向end，慢指针指向mid， 然后快指针逆序指会mid，
 *  n1指针从头开始， n2指针从尾开始，比对，如果一样，则是回文，  空间复杂度为O(1) ,时间复杂度为O(n)
 */
public class 判断链表是否是回文 {

    public static class Node{
        public int value;
        public Node next;
        public Node(int data){
            this.value = data;
        }
    }

    public static boolean isPalindrome(Node head){
        if(head == null || head.next == null){
            return false;
        }
        //定义快慢指针
        Node  n1 = head;
        Node  n2 = head;

        //快慢指针循环 ， n1指向mid， n2 指向end
        while(n2.next != null && n2.next.next != null){
            n1 = n1.next;
            n2 = n2.next.next;
        }

        n2 = n1.next;
        n1.next = null;
        Node n3 = null;
        //右边部分逆序
        while(n2 != null){
            n3 = n2.next;
            n2.next  = n1 ;
            n1 = n2;
            n2 = n3;
        }

        n3 = n1 ;
        n2 = head;
        boolean res = true;
        //比对值是否一样
        while (n1 != null && n2 !=null){
            if(n1.value != n2.value){
                res = false;
                break;
            }
            n1 = n1.next;
            n2 = n2.next;
        }

        //右边重新恢复原样，逆序
        n1 = n3.next;
        n3.next = null;
        while(n1 != null){
            n2 = n1.next;
            n1.next = n3;
            n3 = n1 ;
            n1 = n2;
        }

        return res;
    }


    public static void main(String[] args) {
        Node head = new Node(1);
        Node next1 = new Node(2);
        Node next2 = new Node(3);
        Node next3 = new Node(4);
        Node next4 = new Node(2);
        Node next5 = new Node(1);
        head.next = next1;
        next1.next = next2;
        next2.next = next3;
        next3.next = next4;
        next4.next = next5;

        System.out.println(isPalindrome(head));



    }

}
